When "circuit extraction" programs are applied to an IC layout design database, the result is a representation of the electrical circuit which would result from committing that layout design to a mask set and fabricating integrated circuit chips using that mask set. While their internal representations differ, all circuit extraction programs must, at one point, determine all disjoint sets of polygons representing areas of equipotential in the final, fabricated IC, i.e., they must determine all electrical nodes represented in the design database.
If polygons representing the same conductive material touch or overlap each other, then they represent an electrical node. Similarly, if polygons representing different conductive materials are shown to be "connected" by either proximity or so-called "contact" materials, then they, too, represent an electrical node. The polygons that comprise an electrical node may be formed or represented for analysis purposes in any one of several ways that are commonly known in the art. Incorrect placement of conductive or contact materials results in the connection of one node to another, and if only geometric information is available to the programs analyzing the layout information, then it is typically not possible to precisely locate the position of the incorrectly placed polygon(s). As an example, FIG. 1 represents a node comprised of polygons 1,2,3,4 and 5. It is not possible to tell that it is, in fact, formed of two nodes, A and B as shown in FIG. 2, shorted together by the polygon labelled "3".
Certain known software routines that are commercially available assist in identifying layout errors causing electrical nodes to be incorrectly connected. In one software routine the shortest conductive path is formed between two points (on an electrical node) selected by the user from the "extracted network". This path is displayed, and the task of the user is to determine the incorrect polygon(s) which caused the points to connect. FIGS. 1-3 represent an example of the type of problem solved by this technique. Specifically, in FIG. 1, an electrical node comprised of 5 polygons (numbered 1-5) are extracted from the layout. The polygon 3 was placed in error to connect nodes A and B, as shown in FIG. 2. When the user operates the program to display the short between the two points A and B, polygons 2, 3, and 4 are highlighted, and the user's job is then to determine that polygon 3 is incorrectly placed. The conventional program determines all paths (shorts) among the different nodes identified by the user. They may all be displayed simultaneously or in the order of increasing "length" (i.e., the number of polygons or trapezoids comprising them). FIGS. 5B-D show the sequence of displays which would result from a user's effort to separate the two nodal components of the "figure-eight" node shown in FIG. 5A. FIG. 5E shows the initial result of conventional program operation to locate the shorts and display all paths that are found simultaneously.
Another known software routine "prunes" from the extracted node under analysis (the "problem node") all non-ambiguous branches. The extracted node in FIG. 1 comprises polygons 1-5. If the user indicates that, as in FIG. 3, point (a) corresponds to A POINT ON NODE A, and that point (b) corresponds to A POINT ON NODE B, then the ambiguity of the node can be reduced to the area shown in FIG. 4 as "?" because the polygons 1,2,4 and 5 can be "pruned" away since they are now known to no longer belong to ambiguous branches of the problem node. The remaining area is (in this trivial example) sufficiently simple for the user to determine the cause of the short. If not, then the user may enter additional points of correspondence to further reduce the ambiguity of the problem node in the manner previously described. Such known programs for operation on conventional main frame and workstation computers are available from Cadence Design Systems, Inc. of San Jose, Calif.
One disadvantage encountered with each of the aforementioned programs is that insufficient information is provided to the user to quickly "home-in" on the error, unless the node is extremely simple (such as in the example), or unless the user's placement of known nodal points is fortuitous. Another difficulty encountered is that these known programs do not deal effectively with the typical case in which multiple nodes are shorted in multiple locations, and the only points easily available to the user are at or near the connection pads of the chip. Nodes such as those delivering power to a chip, or clock lines, or ground, can be extremely large and complex, comprising thousands, hundreds of thousands, or (in future chips) millions of individual polygons. Two or more of such nodes may be shorted together in more than one place, exacerbating the problem. Indeed, any number of nodes may have inadvertently been shorted together in any number of places, thus creating a problem that is difficult to solve without a major advancement in analysis techniques.